/**
 * @file 416.PartitionEqualSS.cc
 * @author snow-tyan (zziywang@163.com)
 * @brief {Life is too short to learn cpp.}
 * @version 0.1
 * @date 2021-11-24
 * 
 * @copyright Copyright (c) 2021
 * 
 * 0-1背包问题
 * 416.分割等和子集
 * 494.目标和
 * 1049.最后一块石头重量II
 * 
 * // 特殊多重背包
 * 474.一和零
 * 879.盈利计划
 */

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

template <typename T>
void print(const T &Containers)
{
    typename T::const_iterator it = Containers.begin();
    while (it != Containers.end()) {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
}

class Solution
{
public:
    // 416.
    bool canPartition(const vector<int> &nums)
    {
        // 0-1背包，背包容量为sum/2
        // dp[i][j] 表示遍历到nums[i],背包容量j时 能否和为target
        // dp[i][j]=dp[i-1][j] | dp[i-1][j-nums[i]] 能或不能
        int sum = 0;
        for (auto &num : nums) {
            sum += num;
        }
        if (sum % 2 != 0) {
            return false;
        }
        int target = sum / 2;
        vector<int> dp(target + 1, false); // bool 没有 |= 重载？？？
        dp[0] = true;
        for (int i = 0; i < nums.size(); ++i) {
            for (int j = target; j >= nums[i]; --j) {
                dp[j] |= dp[j - nums[i]];
            }
        }
        return dp[target];
    }
    // 494.
    int findTargetSumWays(const vector<int> &nums, int S)
    {
        //一模一样，返回的是个数
        // dp[i][j] 以nums[i]结尾，和为j的方案个数
        // dp[i][j]=dp[i-1][j]+dp[i-1][j-nums[i]]
        int sum = 0;
        for (auto &num : nums) {
            sum += num;
        }
        if (sum + S < 0 || (sum + S) % 2 != 0) {
            return 0;
        }
        int target = (sum + S) / 2;
        vector<int> dp(target + 1, 0);
        dp[0] = 1;
        for (int i = 0; i < nums.size(); ++i) {
            for (int j = target; j >= nums[i]; --j) {
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[target];
    }
    // 1049.
    int lastStoneWeightII(const vector<int> &stones)
    {
        // 把石头分成两堆，一堆多，一堆少
        // sumA - sumB = res 我们要求最少的res (res>=0)
        // sumA + sumB = sum
        // 下式减上式，2 * sumB = sum - res <= sum
        // 记sumB为target，target最有最大值sum/2 (sum/2这里向下取整，所以是sumB)
        // dp[j] 容量为j的背包，能装的石头价值 (这里石头价值=重量)
        // 我们想尽量让dp[j]更大，所以dp[j] = max(dp[j],dp[j-stone]+stone)
        // 返回值res = sum - 2 * dp[target]
        int sum = 0;
        for (auto &stone : stones) {
            sum += stone;
        }
        int target = sum / 2;
        vector<int> dp(target + 1, 0);
        dp[0] = 0;
        for (int i = 0; i < stones.size(); ++i) {
            for (int j = target; j >= stones[i]; --j) {
                dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
            }
        }
        return sum - 2 * dp[target];
    }
    // 474.
    int findMaxForm(const vector<string> &strs, int m, int n)
    {
        // 可以依然看成0-1背包
        // dp[i][j][k] 前i个字符串，j个0和k个1的最大子集大小
        // dp[j][k]=max(dp[j][k], dp[j-count[0]][k-count[1]])

        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        dp[0][0] = 0;
        for (int i = 0; i < strs.size(); ++i) {
            vector<int> count = countZeroAndOne(strs[i]);
            for (int j = m; j >= count[0]; --j) {
                for (int k = n; k >= count[1]; --k) {
                    dp[j][k] = max(dp[j][k], dp[j - count[0]][k - count[1]] + 1);
                }
            }
        }
        return dp[m][n];
    }

private:
    vector<int> countZeroAndOne(const string &str)
    {
        vector<int> count(2, 0);
        for (auto &ch : str) {
            if (ch == '0') {
                ++count[0];
            } else {
                ++count[1];
            }
        }
        return count;
    }

public:
    // 879.
    int profitableSchemes(int n, int minProfit, const vector<int> &group, const vector<int> &profit)
    {
        // dp[j][k] k名员工共同参与，创造利润j的方案个数
        // dp[j][k]+=dp[k-group[i]][j-profit[i]]

        vector<vector<int>> dp(minProfit + 1, vector<int>(n + 1, 0));
        dp[0][0] = 1;
        int MOD = 1000000007;
        for (int i = 0; i < group.size(); ++i) {
            for (int j = minProfit; j >= 0; --j) { // 利润[minProfit, 0]
                for (int k = n; k >= group[i]; --k) {
                    dp[j][k] += dp[max(0, j - profit[i])][k - group[i]];
                    dp[j][k] %= MOD;
                }
            }
        }
        int sum = 0;
        for (int k = 0; k <= n; ++k) {
            sum += dp[minProfit][k];
        }
        return sum % MOD;
    }
};

void test416()
{
    cout << Solution().canPartition({1, 5, 11, 5}) << endl;
    cout << Solution().canPartition({1, 2, 3, 5}) << endl;
}

void test494()
{
    cout << Solution().findTargetSumWays({1, 1, 1, 1, 1}, 3) << endl;
    cout << Solution().findTargetSumWays({1}, 1) << endl;
}

void test1049()
{
    cout << Solution().lastStoneWeightII({2, 7, 4, 1, 8, 1}) << endl;
    cout << Solution().lastStoneWeightII({31, 26, 33, 21, 40}) << endl;
}

void test474()
{
    cout << Solution().findMaxForm({"10", "0001", "111001", "1", "0"}, 5, 3) << endl;
    cout << Solution().findMaxForm({"10", "0", "1"}, 1, 2) << endl;
}

void test879()
{
    cout << Solution().profitableSchemes(5, 3, {2, 2}, {2, 3}) << endl;
    cout << Solution().profitableSchemes(10, 5, {2, 3, 5}, {6, 7, 8}) << endl;
}

int main()
{
    // test416();
    // test494();
    // test1049();
    // test474();
    test879();
    return 0;
}